每个工具对答案的贡献为 \(\min(a-1,x_{i})\)，并且答案可能会爆 \(long\)，状态好差，WA 两次。
1
2
3
4
5
6
7
8
| public static void solve() {
int a = io.nextInt(), b = io.nextInt(), n = io.nextInt();
long ans = b;
for (int i = 0; i < n; i++) {
ans += Math.min(a - 1, io.nextInt());
}
io.println(ans);
}
|
数学题。当 \(k\bmod 2=1\) 时，先手会得到 \(\min(0,maxb-mina)\)；反之，后手此时必然有最小价值的苹果 \(\min(mina,minb)\)，而先手此时会有最大价值的苹果 \(\max(maxa,maxb)\)，做一次交换即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public static void solve() {
int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
long suma = 0L;
int mina = Integer.MAX_VALUE, maxa = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int x = io.nextInt();
suma += x;
mina = Math.min(mina, x);
maxa = Math.max(maxa, x);
}
int minb = Integer.MAX_VALUE, maxb = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
int x = io.nextInt();
minb = Math.min(minb, x);
maxb = Math.max(maxb, x);
}
if (k % 2 == 1) {
io.println(suma + Math.max(0, maxb - mina));
} else {
io.println(suma + Math.max(0, maxb - mina) - Math.max(maxa, maxb) + Math.min(mina, minb));
}
}
|
完了，官方解法看不懂，下面是我的解法，就是一直乘二求余，贪心的拆分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
int x = n % m, y = m / gcd(n, m);
if ((y & (y - 1)) != 0) {
io.println(-1);
return;
}
long ans = 0L;
while (x != 0) {
ans += x;
x *= 2;
x %= m;
}
io.println(ans);
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
|
下面是官解，大概懂了。\(\frac{a}{b}\) 表示最终每个人得到的苹果价值的小数部分（可以表示为 \(\sum_{i\in S}\frac{1}{2^{i}}\)），因为 \(b\) 必须是二的幂，所以 \(a\) 中 \(1\) 的个数就表示这个人所需的最小苹果片数（就是集合 \(S\) 中元素的个数），乘以 \(m\) 就表示最后总共的苹果片数，然后减去最开始的 \(n\) 片就是需要进行操作的次数（因为每次操作会增加 \(1\) 片）。（这个题解很详细，提供了另一种视角）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void solve() {
int n = io.nextInt(), m = io.nextInt();
n %= m;
int x = gcd(n, m), a = n / x, b = m / x;
if ((b & (b - 1)) != 0) {
io.println(-1);
} else {
io.println((long) Integer.bitCount(a) * m - n);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
|
其实是很简单的动态规划，但就是动不起来啊。定义 \(dp[i]\) 为将 \(MEX\) 变为 \(i\) 需要的最小代价，然后从大到小转移即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private static final int N = 5001;
public static void solve() {
int n = io.nextInt();
int[] cnt = new int[N];
for (int i = 0; i < n; i++) {
int x = io.nextInt();
if (x < n) cnt[x]++;
}
int mex = 0;
while (cnt[mex] > 0) mex++;
long[] dp = new long[mex + 1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[mex] = 0;
for (int i = mex - 1; i >= 0; i--) {
for (int j = i + 1; j <= mex; j++) {
dp[i] = Math.min(dp[i], dp[j] + (long) (cnt[i] - 1) * j + i);
}
}
io.println(dp[0]);
}
|